/*
 * Copyright (C) 2011-2013 Eric Lasota
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#ifndef __TDP_HASHMAP_HPP__
#define __TDP_HASHMAP_HPP__

#include "rdx_basictypes.hpp"
#include "rdx_objectmanagement.hpp"
#include "rdx_utility.hpp"
#include "rdx_longflow.hpp"
#include "rdx_blockcopy.hpp"

using namespace RDX::ObjectManagement;

namespace RDX
{
	namespace Collections
	{
		struct HashElement
		{
			enum HashElementType
			{
				HMT_ElementTypeEmpty,			// Empty bucket, terminates probe
				HMT_ElementTypeDeleted,			// Empty bucket, won't terminate probe

				HMT_ContainsData,

				HMT_ElementTypeFilled,			// Bucket with a value
				HMT_ElementTypeLoose,			// Unsorted value
			};

			HashElementType elementType;
			HashValue hash;
		};

		template<class Tk, class Tv>
		struct HashEntry
		{
			HashElement e;
			Tk k;
			Tv v;
		};

		template<class Tk, class Tv>
		struct HashMapSimple
		{
			typedef Tk HTKey;
			typedef Tk CandidateKey;
			typedef Tv Value;
			typedef HashEntry<Tk,Tv> HTEntry;

			struct NativeProperties
			{
				HTEntry *untracedEntries;
				LargeInt numEntries;
				ObjectManagement::IObjectManager *objectManager;
			} _native;

			inline void InitializeElement(HashEntry<Tk,Tv> *v)
			{
				memset(v, 0, sizeof(HashEntry<Tk,Tv>));
			}

			inline LargeInt UnitSize() const
			{
				return sizeof(HashEntry<Tk,Tv>);
			}

			inline HashEntry<Tk,Tv> *EntryElement(LargeInt idx)
			{
				return &_native.untracedEntries[idx];
			}

			inline const HashEntry<Tk,Tv> *EntryElement(LargeInt idx) const
			{
				return &_native.untracedEntries[idx];
			}

			inline bool CompareKey(const Tk *ckey, const HashEntry<Tk,Tv> *e) const
			{
				return ckey[0] == e->k;
			}

			inline HashValue HashCKey(const Tk *ckey) const
			{
				return Utility::HashBytes(ckey, sizeof(Tk));
			}

			inline void SwapEntryData(LargeInt entry1idx, LargeInt entry2idx, LargeInt swapEntryIdx)
			{
				if(entry1idx == entry2idx)
					return;

				HashEntry<Tk,Tv> *swapEntry = EntryElement(swapEntryIdx);
				HashEntry<Tk,Tv> *entry1 = EntryElement(entry1idx);
				HashEntry<Tk,Tv> *entry2 = EntryElement(entry2idx);

				*swapEntry = *entry1;
				*entry1 = *entry2;
				*entry2 = *swapEntry;
			}

			inline void ReadValue(LargeInt index, Tv *value) const
			{
				value[0] = EntryElement(index)->v;
			}

			inline void LoadValue(LargeInt index, const Tv *value)
			{
				EntryElement(index)->v = value[0];
			}

			inline Tk ConstructKey(OperationContext *ctx, const Tk *ckey, bool &recheck)
			{
				recheck = false;
				return *ckey;
			}

			inline Programmability::Type *ArrayType() const
			{
				return NULL;
			}

			inline void SetObjectManager(ObjectManagement::IObjectManager *om)
			{
				_native.objectManager = om;
			}
		};

		template<typename Tbase>
		class HashMap : public Tbase
		{
		private:
			LargeInt load;
			LargeInt loadFactorPercentage;
			ObjectManagement::ITypeProcessor *typeProcessor;

		public:

			inline void Clear()
			{
				if(this->_native.objectManager)
				{
					this->_native.objectManager->GetAllocator()->Realloc(_native.untracedEntries, 0);
					_native.untracedEntries = NULL;
					_native.numEntries = 0;
				}
			}

			inline ~HashMap()
			{
				Clear();
			}

			inline void SetTypeProcessor(ITypeProcessor *tp)
			{
				typeProcessor = tp;
			}

			// Returns the first match of a key.  If not found, returns an index that it can be inserted at
			inline LargeInt FindElementIndex(const typename Tbase::CandidateKey *ckey, HashValue hash, bool &found) const
			{
				const Tbase::HTEntry *entries = _native.untracedEntries;
				if(!entries)
				{
					found = false;
					return 0;
				}

				LargeInt numEntries = _native.numEntries;
				LargeInt idx = HashValueIndex(hash, numEntries);

				LargeInt insertableIndex = 0;
				bool hitInsertable = false;

				for(LargeInt n=0;n<numEntries;n++,idx++)
				{
					if(idx == numEntries)
						idx = 0;

					const HashElement *entry = &EntryElement(idx)->e;
					if(entry->elementType != HashElement::HMT_ElementTypeFilled)
					{
						if(hitInsertable == false)
						{
							hitInsertable = true;
							insertableIndex = idx;
						}
						
						if(entry->elementType == HashElement::HMT_ElementTypeEmpty)
							break;	// Entry doesn't exist

						if(entry->elementType == HashElement::HMT_ElementTypeDeleted)
							continue;	// Keep going
					}

					if(CompareKey(ckey, EntryElement(idx)))
					{
						found = true;
						return idx;
					}
				}

				found = false;
				return insertableIndex;
			}

			inline LargeInt FindElementIndex(const typename Tbase::CandidateKey *ckey, bool &found, HashValue *hashValue) const
			{
				HashValue hash = HashCKey(ckey);

				if(hashValue)
					*hashValue = hash;

				return FindElementIndex(ckey, hash, found);
			}

			inline void DestroyEntry(LargeInt idx)
			{
				InitializeElement(EntryElement(idx));

				EntryElement(idx)->e.elementType = HashElement::HMT_ElementTypeDeleted;
			}

			inline void RemoveEntry(LargeInt idx)
			{
				Tbase::HTEntry *entries = _native.untracedEntries;
				LargeInt numEntries = _native.numEntries;
				HashElement *entry = &EntryElement(idx)->e;

				if(entry->elementType == HashElement::HMT_ElementTypeFilled)
				{
					// If the next entry is empty, then this can be emptied, otherwise it needs to act as a gap filler for probing
					const HashElement *nextEntry = &EntryElement(idx+1)->e;
					if(idx + 1 == numEntries)
						nextEntry = &EntryElement(0)->e;

					if(nextEntry->elementType == HashElement::HMT_ElementTypeEmpty)
						entry->elementType = HashElement::HMT_ElementTypeEmpty;
					else
						entry->elementType = HashElement::HMT_ElementTypeDeleted;
					DestroyEntry(idx);
					load--;
				}
			}

			inline void Balance()
			{
				LargeInt shrinkThreshold = _native.numEntries * loadFactorPercentage / 200;
				if(load > 8 && load < shrinkThreshold)
				{
					LargeInt newCount = _native.numEntries / 2;
					Rehash(_native.numEntries, newCount, _native.numEntries);

					HTEntry *newEntries = _native.objectManager->GetAllocator()->Realloc(_native.untracedEntries, newCount + 1);
					if(newEntries)
						_native.untracedEntries = newEntries;	// Realloc failed, but it was a shrink op, so just reuse
					_native.numEntries = newCount;
				}
			}

			inline HashMap()
			{
				load = 0;
				loadFactorPercentage = 80;
				_native.untracedEntries = NULL;
				_native.numEntries = 0;
				typeProcessor = NULL;
			}

			inline bool ContainsKey(const typename Tbase::CandidateKey *ckey) const
			{
				bool found;
				FindElementIndex(ckey, found, (HashValue *)NULL);
				return found;
			}

			inline bool SetElement(const typename Tbase::CandidateKey *ckey, const typename Tbase::Value *value, HashValue hashValue)
			{
				bool found;
				LargeInt index = FindElementIndex(ckey, hashValue, found);

				if(!found)
					return false;
				LoadValue(index, value);
				return true;
			}

			inline bool SetElement(const typename Tbase::CandidateKey *ckey, const typename Tbase::Value *value)
			{
				bool found;
				LargeInt index = FindElementIndex(key, found);

				if(!found)
					return false;
				LoadValue(index, value);
				return true;
			}

			inline bool GetElement(const typename Tbase::CandidateKey *ckey, typename Tbase::Value *value, HashValue hashValue) const
			{
				bool found;
				LargeInt index = FindElementIndex(ckey, hashValue, found);

				if(!found)
					return false;
				ReadValue(index, value);
				return true;
			}

			inline bool GetElement(const typename Tbase::CandidateKey *ckey, typename Tbase::Value *value, HashValue *hashValue) const
			{
				bool found;
				LargeInt index = FindElementIndex(ckey, found, hashValue);

				if(!found)
					return false;
				ReadValue(index, value);
				return true;
			}
			
			inline bool GetElement(const typename Tbase::CandidateKey *ckey, typename Tbase::Value *value) const
			{
				return GetElement(ckey, value, (HashValue *)NULL);
			}

			inline void EnlargeEntryArray(OperationContext *ctx, LargeInt newCount)
			{
				Tbase::HTEntry *entries = _native.untracedEntries;
				LargeInt oldCount;
				LargeInt newRealCount = newCount+1;
				LargeInt unitSize = UnitSize();

				if(!entries)
					oldCount = 0;
				else
					oldCount = _native.numEntries;

				void *newEntries;
				
				newEntries = _native.objectManager->GetAllocator()->Realloc(_native.untracedEntries, newCount + 1);
				if(!newEntries)
				{
					RDX_LTHROW(ctx, Errors::RDX_ERROR_ALLOCATION_FAILED);
				}

				_native.untracedEntries = static_cast<HTEntry *>(newEntries);
				_native.numEntries = newCount;

				for(LargeInt i=oldCount ; i < newRealCount ; i++)
					InitializeElement(EntryElement(i));
			}

			inline void Insert(OperationContext *ctx, const typename Tbase::CandidateKey *ckey, const typename Tbase::Value *value, HashValue hash)
			{
				RDX_TRY(ctx)
				{
					Tbase::HTEntry *entries = _native.untracedEntries;

					LargeInt numEntries = 0;

					if(entries)
						numEntries = _native.numEntries;

					if(load*100 >= loadFactorPercentage*numEntries)
					{
						LargeInt oldCount = 0;
						if(_native.untracedEntries)
							oldCount = _native.numEntries;

						LargeInt newCount;
						if(!oldCount)
							newCount = 1;
						else
							newCount = oldCount * 2;

						RDX_PROTECT(ctx, EnlargeEntryArray(ctx, newCount));

						entries = _native.untracedEntries;

						Rehash(oldCount, newCount, newCount);
					}

					bool found;
					LargeInt index = FindElementIndex(ckey, hash, found);

					if(found)
					{
						LoadValue(index, value);
					}
					else
					{
						bool recheck;
						HTKey htkey;
						RDX_PROTECT_ASSIGN(ctx, htkey, ConstructKey(ctx, ckey, recheck));

						// If a recheck is required, the hash list may have changed from a rebalance during the GC stage
						if(recheck)
							index = FindElementIndex(ckey, hash, found);

						EntryElement(index)->k = htkey;

						LoadValue(index, value);
					
						EntryElement(index)->e.hash = hash;
						EntryElement(index)->e.elementType = HashElement::HMT_ElementTypeFilled;

						load++;
					}
				}
				RDX_CATCH(ctx)
				{
					RDX_RETHROW(ctx);
				}
				RDX_ENDTRY
			}
			
			inline void Insert(OperationContext *ctx, const typename Tbase::CandidateKey *ckey, const typename Tbase::Value *value)
			{
				HashValue hash = HashCKey(ckey);

				Insert(ctx, ckey, value, hash);
			}

			inline void Rehash(LargeInt oldCount, LargeInt newCount, LargeInt swapIndex)
			{
				Tbase::HTEntry *entries = _native.untracedEntries;

				// Convert all deleted to empty and all filled to loose
				for(LargeInt i=0;i<oldCount;i++)
				{
					HashElement *entry = &EntryElement(i)->e;

					if(entry->elementType == HashElement::HMT_ElementTypeDeleted)
						entry->elementType = HashElement::HMT_ElementTypeEmpty;
					else if(entry->elementType == HashElement::HMT_ElementTypeFilled)
						entry->elementType = HashElement::HMT_ElementTypeLoose;
				}

				for(LargeInt i=0;i<oldCount;i++)
				{
					HashElement *element = &EntryElement(i)->e;

					// As long as this bucket contains a filled element, keep moving it to the proper location
					while(element->elementType == HashElement::HMT_ElementTypeLoose)
					{
						if(element->elementType == HashElement::HMT_ElementTypeEmpty)
							break;

						// Reinsert this element
						LargeInt destination = HashValueIndex(element->hash, newCount);
						while(EntryElement(destination)->e.elementType == HashElement::HMT_ElementTypeFilled)
						{
							destination++;
							if(destination == newCount)
								destination = 0;
						}

						element->elementType = HashElement::HMT_ElementTypeFilled;
						SwapEntryData(i, destination, swapIndex);
					}
				}

				// Reset the swap element
				InitializeElement(EntryElement(swapIndex));
			}
		};

	};
};

#endif
